{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## _*Using Qiskit Aqua for exact cover problems*_\n",
    "\n",
    "In mathematics, given a collection $S$ of subsets of a set $X$.\n",
    "An exact cover is a subcollection $S_{ec} \\subseteq S$ such that each element in $X$ is contained in exactly one subset $\\in S_{ec}$. \n",
    "\n",
    "We will go through two examples to show:\n",
    "1. How to run the optimization\n",
    "2. How how to run the optimization with the VQE."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The problem and the brute-force method.\n",
    "\n",
    "First, let us take a look at the list of subsets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 3, 4], [1, 2], [3, 4], [1, 2, 3]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import json\n",
    "\n",
    "from qiskit import BasicAer\n",
    "from qiskit.aqua.algorithms import NumPyMinimumEigensolver\n",
    "from qiskit.optimization.applications.ising import exact_cover\n",
    "from qiskit.optimization.applications.ising.common import sample_most_likely\n",
    "\n",
    "input_file = 'sample.exactcover'\n",
    "with open(input_file) as f:\n",
    "    list_of_subsets = json.load(f)\n",
    "    print(list_of_subsets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we apply the brute-force method. Basically, we exhaustively try all the binary assignments. In each binary assignment, the entry of a subset is either 0 (meaning the subset is not in the cover) or 1 (meaning the subset is in the cover). We print the binary assignment that satisfies the definition of the exact cover."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is [0, 1, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "def brute_force():\n",
    "    # brute-force way: try every possible assignment!\n",
    "    has_sol = False\n",
    "\n",
    "    def bitfield(n, L):\n",
    "        result = np.binary_repr(n, L)\n",
    "        return [int(digit) for digit in result]  # [2:] to chop off the \"0b\" part\n",
    "\n",
    "    L = len(list_of_subsets)\n",
    "    max = 2**L\n",
    "    for i in range(max):\n",
    "        cur = bitfield(i, L)\n",
    "        cur_v = exact_cover.check_solution_satisfiability(cur, list_of_subsets)\n",
    "        if cur_v:\n",
    "            has_sol = True\n",
    "            break\n",
    "    return has_sol, cur\n",
    "\n",
    "has_sol, cur = brute_force()\n",
    "if has_sol:\n",
    "    print(\"Solution is\", cur)\n",
    "else:\n",
    "    print(\"No solution is found\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "qubit_op, offset = exact_cover.get_operator(list_of_subsets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part I: Run the optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is [0 1 1 0]\n"
     ]
    }
   ],
   "source": [
    "algo = NumPyMinimumEigensolver(qubit_op, aux_operators=[])\n",
    "result = algo.run()\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = exact_cover.get_solution(x)\n",
    "np.testing.assert_array_equal(ising_sol, [0, 1, 1, 0])\n",
    "\n",
    "if exact_cover.check_solution_satisfiability(ising_sol, list_of_subsets):\n",
    "    print(\"Solution is\", ising_sol)\n",
    "else:\n",
    "    print(\"No solution is found\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part II: Run the optimization with the VQE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution is [0. 1. 1. 0.]\n"
     ]
    }
   ],
   "source": [
    "from qiskit.aqua import aqua_globals\n",
    "from qiskit.aqua.algorithms import VQE\n",
    "from qiskit.aqua.components.optimizers import COBYLA\n",
    "from qiskit.circuit.library import TwoLocal\n",
    "\n",
    "aqua_globals.random_seed = 10598\n",
    "\n",
    "optimizer = COBYLA()\n",
    "var_form = TwoLocal(qubit_op.num_qubits, 'ry', 'cz', reps=5, entanglement='linear')\n",
    "vqe = VQE(qubit_op, var_form, optimizer)\n",
    "\n",
    "backend = BasicAer.get_backend('statevector_simulator')\n",
    "result = vqe.run(backend)\n",
    "\n",
    "x = sample_most_likely(result.eigenstate)\n",
    "ising_sol = exact_cover.get_solution(x)\n",
    "if exact_cover.check_solution_satisfiability(ising_sol, list_of_subsets):\n",
    "    print(\"Solution is\", ising_sol)\n",
    "else:\n",
    "    print(\"No solution is found\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
